/*
 * 0-1_Knapsack_Problem.cpp
 * 	01背包问题
 * 	状态转移公式：
 * 	opt[capacity(i), i]
 * 	 =  MAX (opt[capacity(i), i-1] ,					//这是表示i不放进包中的情况
 * 	 		opt[capacity(i)-weight(i), i-1] + price(i)  //这是i放进包中的情况，此时前i-1个元素就只用掉了capacity(i)-weight(i)的空间
 * 	 		)
 *  Created on: 2012-5-10
 *      Author: xubin
 */

#include <iostream>
#include <vector>
using namespace std;

class KnapsackProblem {
private:
	int capacity;
	vector<int> weight;
	vector<int> price;

public:
	KnapsackProblem() {
		int w[] = { 1, 2, 3 };
		int p[] = { 5, 4, 10 };
		capacity = 4;		//把这里写成了int capacity=4，结果没有对private的capacity变量赋值，错了很久，查了很久。
		weight = vector<int>(w, w + sizeof(w) / sizeof(int));
		price = vector<int>(p, w + sizeof(p) / sizeof(int));

	}

	int solve() {
		vector<vector<int> > opt(weight.size(), vector<int>(capacity + 1, 0)); //这里capacity+1, 因为本来是从1 到 capacity，但后面我们把0也要用上。
		int i;
		int j;

		/*
		 * 下面的做法是把opt[i][0] ....opt[i][capacity]都算出来
		 * 感觉实际上好像可以不算全部算出来，不过不想再试了。
		 */
		//单独处理i=0的情况
		for (j = 1; j <= capacity; j++) {
			if (j >= weight[0]) {
				opt[0][j] = price[0];
			}
		}

		//上面这一步相当于处理了 i=0的情况，这里我们从i=1开始处理
		for (i = 1; i < weight.size(); i++) {
			for (j = 1; j <= capacity; j++) {
				if (j >= weight[i]) {
					opt[i][j] = max(opt[i - 1][j],
							opt[i - 1][j - weight[i]] + price[i]);
				} else {
					opt[i][j] = opt[i - 1][j];		//j不够大，也就是空间根本不够放进第i个元素，所以不考虑这第i个元素
				}

			}
		}

		debug(opt);
		cout << opt[opt.size() - 1][opt[0].size() - 1] << endl;
		return 1;
	}

	static int max(int a, int b) {
		return (a > b ? a : b);
	}

	static int debug(const vector<vector<int> > &v) {
		int i;
		int j;
//		cout<<v[1].size()<<endl;
//		return 1;
		for (i = 0; i < v[0].size(); i++) {
			for (j = 0; j < v.size(); j++) {
				cout << v[j][i] << ", "; //v[j][i]而不是v[i][j]
			}
			cout << endl;
		}
		cout << "-------------" << endl;
	}

};

int main() {
	KnapsackProblem k;
	k.solve();
}
